The present invention is directed to an information storage apparatus adaptable for first-in-first-out storage and output of information packets. In particular, the present invention is an information storage apparatus which is particularly amenable to implementation in large sizes without adding to propagation delay.
Prior art storage devices effecting a first-in-first-out (FIFO) mode of operation, such as the device disclosed in U.S. Letters Pat. No. 4,805,139, "Propagating FIFO Storage Device", issued to the same inventor and assigned to the same assignee as the present application, provide for input of information packets at a first cell in a plurality of cells making up the FIFO storage device. Clock signals control the propagation of information through the plurality of cells making up the FIFO storage device until the information packets reach the output of the device. Thus, by adding a greater capacity to the prior art devices, in the form of a greater number of storage cells, the propagation delay in passing information packets through the storage device is increased.
The FIFO operation of the present invention results in a queueing of information packets in successive storage cells from the output o the apparatus while awaiting a clock signal to transmit an information packet from the output. It is useful to regard such a queue of information packets as a "stack" of information packets, with the bottom of the stack adjacent the output of the apparatus and the top of the stack being the information packet most distal from the output.
The present invention overcomes the disadvantage of increased propagation time with increased size of the storage device. The present invention employs a control circuit, which detects the top of the stack of information packets within the storage cells, and an input means, which directs newly arriving information packet directly to the next available empty storage cell nearest the output of the device (i.e., to the top of the stack). Thus, the previously inherent trade-off of increased propagation time for increased storage capacity is eliminated.